1
Dasar Geometris dari Optimisasi Konveks
MATH008Lesson 8
00:00
Bayangkan berada di tengah lanskap yang rumit, di mana tujuan Anda adalah menemukan titik terdekat menuju keamanan. Dalam istilah optimisasi, 'keamanan' ini merupakan suatu himpunan $C$, dan tindakan mencari titik terdekat merupakan proyeksi. Meskipun intuisi mengatakan selalu ada satu titik 'terdekat' yang unik, kenyataan matematisnya jauh lebih halus. Fondasi geometris dari optimisasi konveks didasarkan pada formalisasi 'kemiripan', melampaui intuisi Euclidean menuju representasi fungsional yang ketat seperti fungsi indikator dan fungsi dukungan.

1. Proyeksi dan Jarak

Jarak dari suatu titik $x_0$ ke himpunan $C$ didefinisikan sebagai infimum dari semua jarak yang mungkin ke titik-titik dalam himpunan tersebut:

$\text{dist}(x_0, C) = \inf\{\|x_0 - x\| \mid x \in C\}$

Operator proyeksi yang mencapai jarak ini adalah optimisasi khusus:

$P_C(x_0) = \text{argmin}\{\|x - x_0\| \mid x \in C\}$

Untuk bidang hiperplana sederhana yang didefinisikan oleh $a^T x = b$, proyeksi memiliki solusi bentuk tertutup yang indah: $P_C(x_0) = x_0 + (b - a^T x_0)a/\|a\|_2^2$. Namun, untuk himpunan umum, ini tetap menjadi masalah optimisasi terbatas: minimalkan $\|x - x_0\|$ dengan kendala $f_i(x) \leq 0$ dan $Ax = b$.

2. Geometri Fungsional

Untuk memperlakukan kendala geometris sebagai komponen objektif, kita menggunakan dua 'cermin' fungsional yang kuat:

  • Fungsi Indikator $I_C(x)$: $I_C(x) = \begin{cases} 0 & x \in C \\ +\infty & x \notin C \end{cases}$. Ini mengubah geometri menjadi hukuman numerik.
  • Fungsi Dukungan $S_C(x)$: $S_C(x) = \sup_{y \in C} x^T y$. Ini mendefinisikan himpunan berdasarkan bidang hiperplana pembatas di setiap arah.
Teorema: Teorema Motzkin

Himpunan tidak kosong dan tertutup $C \in \mathbf{R}^n$ adalah himpunan Chebyshev (yang memiliki proyeksi unik untuk setiap $x_0$) jika dan hanya jika ia adalah konveks.

Sketsa Bukti (Kesatuan)

Misalkan $C$ konveks dan norma bersifat ketat konveks. Jika terdapat dua titik terdekat yang berbeda $u, v \in C$ dengan $\|u - x_0\| = \|v - x_0\| = d$, maka titik tengah mereka $w = (u+v)/2$ berada di $C$ (berdasarkan konveksitas).

Berdasarkan konveksitas ketat dari norma: $\|w - x_0\| = \|\frac{1}{2}(u - x_0) + \frac{1}{2}(v - x_0)\| < \frac{1}{2}\|u - x_0\| + \frac{1}{2}\|v - x_0\| = d$.

Ini bertentangan dengan asumsi bahwa $d$ adalah jarak minimum. Oleh karena itu, proyeksi harus unik.

Catatan Penting 8.4: Ketergantungan Norma

Kita sering membuat bidang hiperplana pemisah menggunakan: $(P_C(x_0) - x_0)^T (x - (1/2)(x_0 + P_C(x_0))) = 0$. Hati-hati! Konstruksi khusus ini hanya valid hanya untuk norma Euclidean. Norma umum memerlukan pendekatan yang lebih halus terhadap ortogonalitas.

šŸŽÆ Inti Utama
Konveksitas adalah 'perekat' yang menjamin stabilitas dalam optimisasi geometris. Tanpa konveksitas, bahkan tugas sederhana 'menemukan titik terdekat' dapat menghasilkan solusi ganda yang saling bertentangan, menyebabkan ketidakstabilan algoritma.